#!/usr/bin/python2

"""

Look at Player.make_all_decisions(). That's the only part of strategy. The rest
is just tracking.
"""

# TODO: handle reputation crossing by resetting the histories for those players to
# empty list

# TODO: compute the recent reputation based on reputation history.



WORST_OUTCOME = -3

# "The first round number we send to hunt_choices is 1."
FIRST_ROUND = 1


def closest_int(number):
    """

    >>> closest_int(4.1)
    4

    >>> closest_int(3.9)
    4

    >>> closest_int(3.5)
    4

    >>> type(closest_int(4.0))
    <type 'int'>

    """
    return int(round(number))


def average(numbers):
    """

    >>> average([10, 20, 60])
    30.0

    >>> average(range(10))
    4.5

    """
    return float(sum(numbers)) / len(numbers)


def at_percentile(percentile, numbers):
    """

    :param percentile: float p: 0 <= p <= 1
    :param numbers: sorted list of numbers
    :return: value in the list `numbers` at the `percentile`th percentile

    >>> at_percentile(0.1, range(1, 11))
    2
    >>> at_percentile(0.1, range(1, 13))
    2
    >>> at_percentile(0.3, range(1, 20))
    6

    >>> at_percentile(0, range(1, 13))
    1
    >>> at_percentile(0.001, range(1, 13))
    1

    >>> at_percentile(1, range(1, 13))
    12
    >>> at_percentile(0.999, range(1, 13))
    12

    >>> at_percentile(0.5, ['a', 'b', 'c'])
    'b'
    >>> at_percentile(0.5, ['a', 'b', 'c', 'd'])
    'c'
    >>> at_percentile(0.5, ['a', 'b', 'c', 'd', 'e'])
    'c'
    >>> at_percentile(0.8, ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
    'g'

    """
    if percentile == 1.0:
        return numbers[-1]

    if percentile == 0.0:
        return numbers[0]

    percentile = float(percentile)
    size = len(numbers)

    rank = (percentile * (size - 1))

    return numbers[closest_int(rank)]


def at_percentile_unsorted(percentile, numbers):
    """

    :param percentile: float p: 0 <= p <= 1
    :param numbers: list of numbers
    :return: value in the list `numbers` at the `percentile`th percentile

    >>> at_percentile_unsorted(0.5, ['c', 'b', 'a'])
    'b'
    >>> at_percentile_unsorted(0.5, ['c', 'a', 'd', 'b'])
    'c'
    >>> at_percentile_unsorted(0.5, ['e', 'b', 'd', 'a', 'c'])
    'c'

    """
    return at_percentile(percentile, sorted(numbers))


def weighted_mean(values_and_weights):
    """

    >>> weighted_mean([(100, 1), (130, 2)])
    120.0
    """
    total_weight = 0.0
    total_value = 0.0
    for value, weight in values_and_weights:
        total_value += value * weight
        total_weight += weight
    return float(total_value) / total_weight


def get_next_rep(rep, total_decisions, num_players):
    """ Returns the min and max possible reputation for a player for next
    round given the current reputation of the player, the total number of
    decisions made by the player so far and the total number of players in the
    next round.

    >>> get_next_rep(0.75, 4, 2)
    (0.6, 0.8)
    >>> # 4 decisions so far and rep is 0.75 ==> 3 'h' and 1 's'
    >>> # 2 players left ==> 1 more decision to take.
    >>> # if decision is 'h' then next rep is 4/5, else 3/5

    >>> get_next_rep(0.6, 10*9, 10)  # 10 players, 1 round
    (0.5454545454545454, 0.6363636363636364)

    >>> get_next_rep(0.6, 1000*999, 1000)  # 1000 players, 1 round
    (0.5994005994005994, 0.6003996003996004)
    >>> # there are 1000 players between 0 and 1, so this is NOT precise

    >>> get_next_rep(0.6, 10*1000*999, 1000)  # 1000 players, 10 rounds
    (0.5999400059994, 0.6000399960003999)

    """
    num_hunts = rep * total_decisions
    next_total_decisions = total_decisions + num_players - 1
    next_rep_min = float(num_hunts) / next_total_decisions
    next_rep_max = float(num_hunts + num_players - 1) / next_total_decisions
    return (next_rep_min, next_rep_max)


# The following 3 functions work well together:
# rep_list == get_unsorted_list(sorted(rep_list), get_indices(rep_list))
def get_sorting_indices(rep_list):
    """ Return a list of indices to "unsort" the reputations list.

    >>> get_sorting_indices([0.5, 0.3, 0.8, 0.2])
    [3, 1, 0, 2]
    """
    return sorted(range(len(rep_list)), key=rep_list.__getitem__)

def get_unsorted_list(rep_list, sorting_indices):
    """ Unsort the list according to indices.

    >>> get_unsorted_list([0.2, 0.3, 0.5, 0.8], [3, 1, 0, 2])
    [0.5, 0.3, 0.8, 0.2]
    """
    return [rep for __, rep in sorted(zip(sorting_indices, rep_list))]

def get_sorted_list(rep_list, indices):
    """ Sort the list according to indices.

    >>> get_sorted_list([0.5, 0.3, 0.8, 0.2], [3, 1, 0, 2])
    [0.2, 0.3, 0.5, 0.8]
    >>> get_sorted_list(['a', 'b', 'c', 'd'], [3, 1, 0, 2])
    ['d', 'b', 'a', 'c']
    """
    return [rep_list[i] for i in indices]



class Opponent(object):
    """
    """

    def __init__(self):
        self.reputations = []
        self.history_with_me = []
        self.my_history = []

    def record_reputation(self, rep):
        self.reputations.append(rep)

    def record_his_decision(self, dec):
        self.history_with_me.append(dec)

    def record_my_decision(self, dec):
        self.my_history.append(dec)

    @property
    def reputation(self):
        return self.reputations[-1]

    @property
    def his_last_decision_with_me(self):
        return self.history_with_me[-1]

    @property
    def my_last_decision_with_him(self):
        return self.my_history[-1]


class Me(object):
    """
    """

    def __init__(self):
        self.food_history = []
        self.reputations = []

    def record_food(self, food):
        self.food_history.append(food)

    def record_reputation(self, rep):
        self.reputations.append(rep)

    @property
    def food(self):
        return self.food_history[-1]

    @property
    def reputation(self):
        return self.reputations[-1]


class Tribe(object):
    """
    """

    def __init__(self):
        # min and max possibly remaining food
        # There is a min and a max because we don't know how much negative food
        # player have when they die.
        self.all_min_food = []
        self.all_max_food = []
        # self.all_reputations[r][0] is the smallest reputation of round r.
        self.all_reputations = []
        self.all_m = []
        self.all_num_players = []

        self.round_number = None

    def record_m(self, m):
        self.all_m.append(m)

    def record_min_max_food(self, minfood, maxfood):
        self.all_min_food.append(minfood)
        self.all_max_food.append(maxfood)

    def record_reputations(self, rep):
        self.all_reputations.append(rep)

    def record_num_players(self, P):
        self.all_num_players.append(P)

    def update_round_number(self, round_num):
        self.round_number = round_num

    @property
    def m(self):
        return self.all_m[-1]

    @property
    def P(self):
        return self.all_num_players[-1]

    @property
    def min_food(self):
        return self.all_min_food[-1]

    @property
    def max_food(self):
        return self.all_max_food[-1]

    @property
    def min_max_food(self):
        return self.all_min_food[-1], self.all_max_food[-1]


def find_dead_players(opponents, player_reputations, total_decisions):
    """ Return the list of indices of players that died.

    player_reputation_history and player_reputations must be sorted.
    """
    dead_players = []
    last_num_opponents = len(opponents)
    current_num_opponents = len(player_reputations)
    dead_players_num = last_num_opponents - current_num_opponents

    if dead_players_num > 0:

        # find out what player(s) died based on the reputations
        last_round_reputations = [opp.reputations[-1] for opp in opponents]
        current_round_reputation = sorted(player_reputations)

        for i, last_rep in enumerate(last_round_reputations):

            min_rep, max_rep = get_next_rep(last_rep, total_decisions, current_num_opponents+1)
            current_rep = current_round_reputation[i - len(dead_players)]

            if not min_rep <= current_rep <= max_rep:
                dead_players.append(i)

            if i  - len(dead_players) == len(current_round_reputation) - 1:
                dead_players.append(i+1)

            if len(dead_players) == dead_players_num:
                break

    return dead_players


def get_max_reappearing_food(prev_num_players, num_deaths):

    # any player could loose up to this in the last round:
    max_loss_by_player = WORST_OUTCOME * (prev_num_players - 1)

    # before previous round, players had at least one food.
    # so players who died did so with a food between 0 and max_loss_by_player+1
    # If they died with food < 0, their death reintroduces some food.
    # We want to keep track of the reappearing food.
    max_food_reappearing_by_player = max_loss_by_player + 1
    return max_food_reappearing_by_player * num_deaths


class Tracker(object):
    """ There is no logic here, just tracking of info.
    """

    def __init__(self):

        self.tribe = Tribe()
        self.opponents = None
        self.me = Me()


        # tells how to reorder player_reputations to get a sorted list of reputations.
        # Using numpy syntax: player_reputations[self.indices] == sorted(player_reputations).
        self.indices = None

        # number of decisions each player had to make so far.
        # (This is the same number for all players.)
        self.total_decisions_per_player = 0


    def make_all_decisions(self):
        """ Return decisions for current round and for all players

        :return: list of choices (either 'h' or 's') of length self.tribe.P - 1

        DERIVED CLASSES MUST OVERRIDE THIS METHOD!
        This is the only method you need to override when you inherit from this
        class.
        """
        return 's' * (self.tribe.P - 1)


    def hunt_choices(self, round_number, my_current_food,
                     my_current_reputation, m, player_reputations):
        """
        :param round_number: integer, the number round you are in.
        :param my_current_food: integer, the amount of food you have.
        :param my_current_reputation: float (python's representation of real
            numbers), your current reputation.
        :param m: integer, the threshold cooperation/hunting value for this round.
        :param player_reputations: list of floats, the reputations of all the
            remaining players in the game.

        The ordinal positions of players in this list will be randomized each
        round.
        """

        self.tribe.update_round_number(round_number)
        self.tribe.record_m(m)
        self.tribe.record_num_players(len(player_reputations) + 1)
        self.tribe.record_reputations(sorted(player_reputations))

        self.me.record_food(my_current_food)
        self.me.record_reputation(my_current_reputation)

        if round_number <= FIRST_ROUND:

            self.opponents = [Opponent() for i in range(self.tribe.P - 1)]

            initial_food = 300 * (self.tribe.P - 1) * self.tribe.P
            self.tribe.record_min_max_food(initial_food, initial_food)

        else:

            # delete players that died during the last round
            dead_players = find_dead_players(
                    self.opponents,
                    player_reputations,
                    self.total_decisions_per_player)

            for dead in reversed(dead_players):
                del self.opponents[dead]

            # update food
            prev_min_food, prev_max_food = self.tribe.min_max_food
            min_food = prev_min_food + self.total_food_for_round
            max_food = prev_max_food + self.total_food_for_round
            num_deaths = len(dead_players)
            if num_deaths >= 1:
                prev_num_players = self.tribe.all_num_players[-2]
                max_food -= get_max_reappearing_food(prev_num_players, num_deaths)

            self.tribe.record_min_max_food(min_food, max_food)


        my_decisions = self.make_all_decisions()


        sorted_player_reputations = sorted(player_reputations)
        for opponent, dec, rep in zip(self.opponents, my_decisions, sorted_player_reputations):
            opponent.record_my_decision(dec)
            opponent.record_reputation(rep)

        self.total_decisions_per_player += self.tribe.P - 1

        self.tribe.record_m(m)
        self.tribe.record_num_players(len(player_reputations) + 1)


        # return decisions in the same order as player_reputations
        self.indices = get_sorting_indices(player_reputations)
        my_decisions_in_order = get_unsorted_list(my_decisions, self.indices)
        return my_decisions_in_order


    def hunt_outcomes(self, my_food_earnings):
        """
        :param food_earnings: list of integers, the amount of food earned from the
            last round's hunts.

        The entries can be negative as it is possible to lose food from a hunt.
        The list will be in the same order as the decisions you made in that
        round.
        """

        player_decisions = ['h' if earning >= 0 else 's'
                            for earning in my_food_earnings]

        player_decisions_ordered_by_rep = get_sorted_list(player_decisions, self.indices)

        for opponent, dec in zip(self.opponents, player_decisions_ordered_by_rep):
            opponent.record_his_decision(dec)


    def round_end(self, award, m, number_of_hunts):
        """
        :param award: integer, total food bonus (can be zero) you received due to
            players cooperating during the last round.
        :param m: integer, the threshold cooperation/hunting value for this round.
        :param number_of_hunts: integer, number of times players chose to hunt in
            the last round.

        The amount of food you have for the next round will be
        current_food + sum of all entries of food_earnings + award from round_end.
        """
        # Compute the delta of total food between last round and this round.
        # Does not take deaths into account. (done latter)

        number_of_bets = self.tribe.P * (self.tribe.P - 1)
        number_of_slacks = number_of_bets - number_of_hunts

        food_from_match = number_of_slacks * (-2)
        food_from_award = self.tribe.P * award
        self.total_food_for_round = food_from_match + food_from_award


    def __str__(self):
        return 'tracker'


class Player(Tracker):

    def make_all_decisions(self):
        """ Return decisions for current round and for all players

        THAT'S WHERE THE MAGIC HAPPENS.
        """
        if self.tribe.round_number < FIRST_ROUND + 5:
            return 'h' * (self.tribe.P - 1)

        if self.tribe.P == 2:
            print 'face-to-face'
            return self.face_to_face_strategy()

        # if my food is low, enter emergency mode
        if self.me.food <= - WORST_OUTCOME * (self.tribe.P - 1) * 5:
            print 'emergency. round', self.tribe.round_number
            return self.low_food_strategy()

        return [self.tit_for_tat_strategy(opp) for opp in self.opponents]


    def face_to_face_strategy(self):

        my_food = self.me.food
        his_min_food = self.tribe.min_food - my_food
        his_max_food = self.tribe.max_food - my_food

        print 'my food {}, his food {}-{}'.format(my_food, his_min_food, his_max_food)

        if my_food > his_max_food - WORST_OUTCOME + 1:
            # I could easily win by always slacking. But I am not that guy, so
            # I will do the same as the other player. This still ensures my
            # victory.
            print 'easy'
            return self.opponents[0].his_last_decision_with_me

        elif my_food > his_max_food - WORST_OUTCOME:
            # slack this time. If the other player hunts, I will enter the
            # condition above and cooperate.
            return ['s']

        elif my_food >= his_min_food:
            # I don't know who has more food... Try to make friend.
            # TODO: long term strategy to make friend. 60% hunts?
            print 'I don\'t know'
            return ['h']

        else:
            # I have less food than the other guy. Desperately try to make
            # friend!
            # TODO: long term strategy to desperately make friend. 90% hunt?
            print 'desperate'
            return ['h']


    def low_food_strategy(self):
        # TODO: use earnings during last round too.
        return ['s'] * (self.tribe.P - 1)


    def tit_for_tat_strategy(self, opponent):
        return opponent.his_last_decision_with_me


    def __str__(self):
        return 'abricot'


if __name__ == "__main__":
    import doctest
    doctest.testmod()
